//  不要给我WA WA 叫
//  一定AC
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iomanip>
#include <climits>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
int a[N];
bool sq(int n)
{
     int p1 = sqrt(n);
     return (p1 * p1 == n);
}
bool tr(int n)
{
     int p2 = sqrt(4 * n / sqrt(3));
     return  sqrt(3) / 4 * p2 * p2 == n;    
}
void solve()
{
     int n;
     cin >> n;     
     if(sq(n) && !tr(n)) cout << "0" << endl;
     if(!sq(n) && tr(n)) cout << "1" << endl;
     if(sq(n) && tr(n)) cout << "2" << endl;
     if(!sq(n) && !tr(n)) cout << "3" << endl;
    
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t -- )  solve();
    return 0;
}